<?php
class ksLeaf{
    const MIN_LEAF_SIZE=5;
    public $x;
    public $y;
    public $w;
    public $h;

    // private $_grids;
    private $_id;

    private $_color_config;

    public $leftChild;
    public $rightChild;
    public $room;
    public $halls;      //大厅

    public $room_mode;      //1=rnd;2=max;3=rnd max

    private $_runMode;

    // Construct
    public function ksLeaf($x,$y,$w,$h) {
        // initialize our leaf
        $this->x = $x;
        $this->y = $y;
        $this->w = $w;
        $this->h = $h;
        $this->_runMode = 1;        //debug mode

        if($this->_runMode) {
            $debugMode = get_func_debug_mode(__METHOD__);
            if($debugMode){
                echo 'DEBUG: ' . __FUNCTION__ . '() '.',x='.$x.',y='.$y.',w='.$w.',h='.$h. PHP_EOL; 
                debug_map_part($x,$y,$w,$h); 
            }            
        }
    }

    public function init(&$grids,$v) {
        $grids = array();
        for ($y = 0; $y < $this->h; $y ++) {
            for ($x = 0; $x < $this->w; $x ++) {
                array_push($grids, $v);
            }
        }
        return $grids;
    }

    public function fill(&$grids,$v) {
        $grids = array();
        for ($y = 0; $y < $this->h; $y ++) {
            for ($x = 0; $x < $this->w; $x ++) {
                array_push($grids, $v);
            }
        }
        return $grids;
    }


    public function split() {
        $debugMode = get_func_debug_mode(__METHOD__);
        if($debugMode) echo 'DEBUG: ' . __METHOD__ . '()'. PHP_EOL; 

        // begin splitting the leaf into two children
        if ($this->leftChild != null || $this->rightChild != null)
        return false; // we’re already split! Abort!

        // determine direction of split
        // if the width is >25% larger than height, we split vertically
        // if the height is >25% larger than the width, we split horizontally
        // otherwise we split randomly
        $splitH = $this->_rnd(1,100) > 50 ? true: false;
        if($debugMode) echo 'DEBUG: ' . __FUNCTION__ . '() splitH='.($splitH?'true':'false'). PHP_EOL; 
        if ($this->w > $this->h && $this->h / $this->w >= 0.05)
            $splitH = false;
        else if ($this->h > $this->w && $this->w / $this->h >= 0.05)
            $splitH = true;

        if($debugMode) echo 'DEBUG: ' . __FUNCTION__ . '() splitH='.($splitH?'true':'false'). PHP_EOL; 

        // determine the maximum height or width
        $max = ($splitH ? $this->h : $this->w) - ksLeaf::MIN_LEAF_SIZE; 
        if($debugMode) echo 'DEBUG: ' . __FUNCTION__ . '() max='.$max. PHP_EOL; 

        if ($max <= (ksLeaf::MIN_LEAF_SIZE + $this->_rnd(0,3)) )
            return false; // the area is too small to split any more…

        $split = $this->_rnd(ksLeaf::MIN_LEAF_SIZE, $max); // determine where we’re going to split

        // create our left and right children based on the direction of the split
        if ($splitH){
            $this->leftChild = new ksLeaf($this->x, $this->y, $this->w, $split);            
            $this->rightChild = new ksLeaf($this->x, $this->y + $split, $this->w, $this->h -$split);
        }else{
            $this->leftChild = new ksLeaf($this->x, $this->y, $split, $this->h);
            $this->rightChild = new ksLeaf($this->x + $split, $this->y, $this->w -$split, $this->h);
        }

        $this->_inherit_from_parent($this->leftChild,$this);
        $this->_inherit_from_parent($this->rightChild,$this);

        return true; // split successful!
    }

    public function createRooms(){
        $debugMode = get_func_debug_mode(__METHOD__);
        if($debugMode)
            echo 'DEBUG: ' . __METHOD__ . '()'.$this->x.','.$this->y.','.$this->w.','.$this->h. PHP_EOL; 
        // this function generates all the rooms and hallways for this Leaf and all of its children.
        if ($this->leftChild != null || $this->rightChild != null) {
            // this leaf has been split, so go into the children leafs
            if ($this->leftChild != null) {
                if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() leftChild:'. PHP_EOL; 
                $this->leftChild->createRooms();
            }
            if ($this->rightChild != null) {
                if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() rightChild:'. PHP_EOL; 
                $this->rightChild->createRooms();
            }

            // if there are both left and right children in this Leaf, create a hallway between them
            if ($this->leftChild != null && $this->rightChild != null) {
                $this->createHall($this->leftChild->getRoom(), $this->rightChild->getRoom());
            }

        } else {
            // this Leaf is the ready to make a room
            // $roomSize;
            // $roomPos;
            // the room can be between 3 x 3 tiles to the size of the leaf – 2.
            // place the room within the Leaf, but don’t put it right
            // against the side of the Leaf (that would merge rooms together)

            if($this->room_mode==null){
                $this->room_mode = $this->_rnd(1,2);
            }
            if($this->room_mode==1){
                $jj=($this->w - $this->_rnd(2,$this->w/2))/2;
                $kk=($this->h - $this->_rnd(2,$this->h/2))/2;

                $x1=$this->x + $this->_rnd(1,$jj);
                $y1=$this->y + $this->_rnd(1,$kk);
                $w1=$this->x + $this->w - $x1 - $this->_rnd(1,$jj);
                $h1=$this->y + $this->h - $y1 - $this->_rnd(1,$kk);
            }else if($this->room_mode==2){
                $x1=$this->x + 1;
                $y1=$this->y + 1;
                $w1=$this->w - 2;
                $h1=$this->h - 2;
            }else if($this->room_mode==3){
                $rnd = $this->_rnd(1,4);
                $w1=$this->w - 1;
                $h1=$this->h - 1;
                if($rnd==1){
                    $x1=$this->x;
                    $y1=$this->y;
                }else if($rnd==2){
                    $x1=$this->x +1;
                    $y1=$this->y;

                }else if($rnd==3){
                    $x1=$this->x;
                    $y1=$this->y +1 ;

                }else{
                    $x1=$this->x +1;
                    $y1=$this->y +1;
                }

            }else{
                $x1=$this->x + 1;
                $y1=$this->y + 1;
                $w1=$this->w - 2;
                $h1=$this->h - 2;
            }

            if($w1<0){
                // if($debugMode) 
                    echo 'DEBUG: ' . __FUNCTION__ . '()  w<0'. PHP_EOL;
            }

            if($h1<0){
                // if($debugMode) 
                    echo 'DEBUG: ' . __FUNCTION__ . '()  h<0'. PHP_EOL;
            }

            $this->room = array('x'=>$x1,'y'=>$y1,'w'=>$w1,'h'=>$h1);
            if($debugMode){
                echo 'DEBUG: ' . __FUNCTION__ . '()'.$this->x.','.$this->y.','.$this->w.','.$this->h.','. PHP_EOL; 
                echo 'DEBUG: ' . __FUNCTION__ . '() get room: '.$x1.','.$y1.','.$w1.','.$h1.','. PHP_EOL; 
                echo debug_map_part($this->x,$this->y,$this->w,$this->h,1,$this->_item_color('leaf')); 
                echo debug_map_part($x1,$y1,$w1,$h1,1,$this->_item_color('room')); 
            }
        }
    }


    public function fillMaps(&$map,$id){
        $debugMode = get_func_debug_mode(__METHOD__);
        if($debugMode) echo 'DEBUG: ' . __METHOD__ . '(,#'.$id.')'. PHP_EOL; 

        if($this->_id ==null){
            $this->_id = $id;
        }

        // if ($this->leftChild != null || $this->rightChild != null) {
            // this leaf has been split, so go into the children leafs
            if ($this->leftChild != null) {
                $this->leftChild->fillMaps($map,$this->_id*2+1);
            }
            if ($this->rightChild != null) {
                $this->rightChild->fillMaps($map,$this->_id*2+2);
            }
        // }

        if($debugMode) echo 'DEBUG: ' . __METHOD__ . '(,#'.$id.') get leaf.'. PHP_EOL; 
        $tmpArr = array('x'=>$this->x,'y'=>$this->y,'w'=>$this->w,'h'=>$this->h);
        $this->_fill_map_with_rect($map,$tmpArr,$this->_item_color('leaf'));

        if($debugMode) echo 'DEBUG: ' . __METHOD__ . '(,#'.$id.') get room.'. PHP_EOL; 
        $r = $this->room;
        $this->_fill_map_with_rect($map,$r,$this->_item_color('room'));

        $halls = $this->halls;
        if($halls !=null){
            if($debugMode) echo 'DEBUG: ' . __METHOD__ . '(,#'.$id.') get hall.'. PHP_EOL; 
            $ccid = $this->_item_color('hall');
            if(is_array($halls)){
                foreach ($halls as $key => $value) {
                    $this->_fill_map_with_rect($map,$value,$ccid);
                }
            }            
        }      
    }

    private function _fill_map_with_rect(&$map,$r,$ccid){
        $debugMode = get_func_debug_mode(__METHOD__);
        if($debugMode) echo 'DEBUG: ' . __METHOD__ . '(,'.$r['x'].','.$r['y'].','.$r['w'].','.$r['h'].')'. PHP_EOL; 
        if($map && $r && $map['w'] && $map['grids'] && $r['w'] ) {
            
            for ($iy=0; $iy <+$r['h'] ; $iy++) { 
                for ($ix=0; $ix <+$r['w'] ; $ix++) { 
                    $pos = ($r['y']+$iy) * $map['w'] + $r['x']+$ix;
                    if(isset($map['grids'][$pos])){
                        if( stripos($map['grids'][$pos], $pos.'#'.$ccid)===false){
                            if(get_top_cell_color($map['grids'][$pos]) > $ccid){
                               if($debugMode)
                                    echo 'DEBUG: ' . __METHOD__ . '() ERROR! '.$pos.'#'.$ccid. PHP_EOL;  
                            }

                            $map['grids'][$pos] = $map['grids'][$pos] . ';'. $pos.'#'.$ccid;    
                            // if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() set '.$pos.'#'.$ccid. PHP_EOL; 
                        // }else{
                        //     if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() skip '.$pos.'#'.$ccid. PHP_EOL; 
                        }
                    }else{
                        if($debugMode){
                            echo 'DEBUG: ' . __METHOD__ . '() rectangle:'.print_r($r,true). PHP_EOL; 
                            echo 'DEBUG: ' . __METHOD__ . '() miss pos #'.$pos. PHP_EOL; 
                        }
                    }
                }
            }
        }
    }


    public function getRoom()
    {
        // iterate all the way through these leafs to find a room, if one exists.
        if ($this->room != null)  return $this->room;

        if ($this->leftChild != null) {
            $leftRoom = $this->leftChild->getRoom();
        }
        if ($this->rightChild != null) {
             $rightRoom = $this->rightChild->getRoom();            
        }
        if ($leftRoom == null && $rightRoom == null)
            return null;
        else if ($leftRoom == null)
        return $leftRoom;
        else if ($rightRoom == null)
        return $rightRoom ;
        else if ($this->_rnd(0,10)> 5)
        return $leftRoom;
        else
        return $rightRoom;
    }


    public function createHall($leftRoom,$rightRoom){
        $debugMode = get_func_debug_mode(__METHOD__);
        if($debugMode) echo 'DEBUG: ' . __METHOD__ . '()'. PHP_EOL; 
        //hall 过道，走廊; 大厅，前厅; 娱乐中心，会所
        // 它将选取一对房间并在二者内选中随机点，然后生成一两个两片瓷砖大小的矩形把点连接起来。
        // now we connect these two rooms together with hallways.
        // this looks pretty complicated, but it’s just trying to figure out which point is where and then either draw a straight line, or a pair of lines to make a right-angle to connect them.
        // you could do some extra logic to make your halls more bendy, or do some more advanced things if you wanted.

        $halls = array();

        // $p1=$this->_BSP_rand_xy($leftRoom['x']+1,$leftRoom['y']-2,$leftRoom['x']+$leftRoom['w']+1,$leftRoom['y']+$leftRoom['h']-2);

        // $p2=$this->_BSP_rand_xy($rightRoom['x']+1,$rightRoom['y']-2,$rightRoom['x']+$rightRoom['w']+1,$rightRoom['y']+$rightRoom['h']-2);

        $p1=$this->_BSP_rand_xy($leftRoom['x'],$leftRoom['y'],$leftRoom['x']+$leftRoom['w']-1,$leftRoom['y']+$leftRoom['h']-1);

        $p2=$this->_BSP_rand_xy($rightRoom['x'],$rightRoom['y'],$rightRoom['x']+$rightRoom['w']-1,$rightRoom['y']+$rightRoom['h']-1);


        $w = +$p2['x'] - (+$p1['x']);
        $h = +$p2['y'] - (+$p1['y']);

        if($debugMode) {
            echo 'DEBUG: ' . __METHOD__ . '() p1:'.print_r($p1,true). PHP_EOL; 
            echo 'DEBUG: ' . __METHOD__ . '() p2:'.print_r($p2,true). PHP_EOL; 
            echo 'DEBUG: ' . __METHOD__ . '() w='.$w.', h='.$h. PHP_EOL; 
        }

        if ($w < 0){
            if ($h < 0){
                if ($this->_rnd(1,10) >5){
                    if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w<0,h<0,#1'. PHP_EOL; 
                    array_push($halls, $this->_rectangle($p2['x'], $p1['y'], abs($w), 1) );
                    array_push($halls, $this->_rectangle($p2['x'], $p2['y'], 1, abs($h)));
                }else{
                    if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w<0,h<0,#2'. PHP_EOL; 
                    array_push($halls, $this->_rectangle($p2['x'], $p2['y'], abs($w), 1));
                    array_push($halls, $this->_rectangle($p1['x'], $p2['y'], 1, abs($h)));
                }
            }else if ($h > 0){
                if ($this->_rnd(1,10) >5){
                    if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w<0,h>0,#1'. PHP_EOL; 
                    array_push($halls, $this->_rectangle($p2['x'], $p1['y'], abs($w), 1));
                    array_push($halls, $this->_rectangle($p2['x'], $p1['y'], 1, abs($h)));
                }else{
                    if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w<0,h>0,#2'. PHP_EOL; 
                    array_push($halls, $this->_rectangle($p2['x'], $p2['y'], abs($w), 1));
                    array_push($halls, $this->_rectangle($p1['x'], $p1['y'], 1, abs($h)));
                }
            } else if ($h == 0){
                if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w<0,h=0'. PHP_EOL; 
                array_push($halls, $this->_rectangle($p2['x'], $p2['y'], abs($w), 1));
            }
        }else if ($w > 0){
            if ($h < 0){
                if ($this->_rnd(1,10) >5){
                    if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w>0,h<0,#1'. PHP_EOL; 
                    array_push($halls, $this->_rectangle($p1['x'], $p2['y'], abs($w), 1));
                    array_push($halls, $this->_rectangle($p1['x'], $p2['y'], 1, abs($h)));
                }else{
                    if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w>0,h<0,#2'. PHP_EOL; 
                    array_push($halls, $this->_rectangle($p1['x'], $p1['y'], abs($w), 1));
                    array_push($halls, $this->_rectangle($p2['x'], $p2['y'], 1, abs($h)));
                }
            }else if ($h > 0){  //ok
                if ($this->_rnd(1,10) >5){   //ok
                    if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w>0 h>0 #1'. PHP_EOL; 
                    array_push($halls, $this->_rectangle($p1['x'], $p1['y'], abs($w), 1));
                    array_push($halls, $this->_rectangle($p2['x'], $p1['y'], 1, abs($h)));
                }else{
                    if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w>0 h>0 #2'. PHP_EOL; 
                    array_push($halls, $this->_rectangle($p1['x'], $p2['y'], abs($w), 1));
                    array_push($halls, $this->_rectangle($p1['x'], $p1['y'], 1, abs($h)));
                }
            }else if ($h == 0){
                if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w>0,h=0'. PHP_EOL; 
                array_push($halls, $this->_rectangle($p1['x'], $p1['y'], abs($w), 1));
            }
        }else if ($w == 0){
            if ($h < 0){
                if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w=0,h<0'. PHP_EOL; 
                array_push($halls, $this->_rectangle($p2['x'], $p2['y'], 1, abs($h)));
            }else if ($h > 0){
                if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() w=0,h>0'. PHP_EOL; 
                array_push($halls, $this->_rectangle($p1['x'], $p1['y'], 1, abs($h)));
            }
        }

        $this->halls = $halls;

        if($debugMode){
            echo 'DEBUG: ' . __METHOD__ . '() p1:'.print_r($halls,true). PHP_EOL; 
            foreach ($halls as $key => $value) {
                $x1 = $value['x'];
                $y1 = $value['y'];
                $w1 = $value['w'];
                $h1 = $value['h'];
                echo 'DEBUG: ' . __METHOD__ . '() p1:'.print_r($value,true). PHP_EOL; 
                echo debug_map_part($x1,$y1,$w1,$h1,1,$this->_item_color('hall')); 
            }            
        }

        return $halls;
    }

    public function get_color_config(){
        return $this->_color_config;
    }

    public function set_color_config($leaf,$room=null,$hall=null,$base=null){
        $debugMode = get_func_debug_mode(__METHOD__);
        if($debugMode) echo 'DEBUG: ' . __METHOD__ . '()'. PHP_EOL; 
        if(is_array($leaf)){
            if(isset($leaf['leaf']) && isset($leaf['room']) && isset($leaf['hall']) && isset($leaf['base']) && isset($leaf['sort']) ){
                $this->_color_config = $leaf;    
            }else{
                if($debugMode) echo 'ERROR: ' . __METHOD__ . '() unknow array ! '. PHP_EOL; 
            }            
        }else{
            $this->_color_config =array('leaf'=>$leaf,'room'=>$room,'hall'=>$hall,'base'=>$base);
            $this->_color_config['sort'] = 'hall;room;leaf;base';
        }
        return $this->_color_config;
    }

    /**
    |---------------------------------------------------------------
    | 系列函数
    |---------------------------------------------------------------
    */
    
    private function _inherit_from_parent($kid,$p){
        if(!$kid || !$p) return false;
        if(isset($p->_color_config)){
            $kid->_color_config = $p->_color_config;
        }
        return true;
    }

    private function _item_color($id){
        // if($this->_color_config==null) return false;
        if(isset($this->_color_config[$id])){
            return $this->_color_config[$id];
        }
        return false;
    }

    private function _rnd($min,$max) {
        return mt_rand($min,$max);
    }

    private function _rectangle($x,$y,$w,$h){
        return array('x'=>$x,'y'=>$y,'w'=>$w,'h'=>$h);
    }

    private function _BSP_rand_xy($x1,$y1,$x2,$y2,$opt=0) {
        $debugMode = get_func_debug_mode(__METHOD__);
        if($debugMode) echo 'DEBUG: ' . __METHOD__ . '('.$x1.','.$y1.','.$x2.','.$y2.','.$opt.')'. PHP_EOL; 
        $opt = +$opt;
        if($opt>0){
            $safe_num = +$opt;
        }else{
            $safe_num = 0;
        }
        if($opt<0 || $x1+$safe_num>=$x2-$safe_num || $y1+$safe_num>=$y2-$safe_num ) {
            // if($debugMode) 
                echo 'DEBUG: ' . __METHOD__ . '() opt Error!'. PHP_EOL; 
            return false;
        }
        
        $max = 10;
        while ( $max>0 ) {
            $x = $this->_rnd($x1+$safe_num, $x2-$safe_num );
            $y = $this->_rnd($y1+$safe_num, $y2-$safe_num );
        
            $pos = $y * $this->w + $x;
            // if(isset($this->_grids[$pos])){
                // return array('x'=>$x,'y'=>$y,'id'=>$pos,'safe_num'=>$safe_num);
            // }
            $ret = array('x'=>$x,'y'=>$y,'safe_num'=>$safe_num);
            if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() ret:'.print_r($ret,true).PHP_EOL; 
            return $ret;
            $max--;
        }
        return false;
    }

}


    /**
    |---------------------------------------------------------------
    | 系列函数
    |---------------------------------------------------------------
    */


class ksBSP{
    private $MAX_LEAF_SIZE = 20;
    public $_leafs;

    // Construct
    public function ksBSP() {
        // initialize 
        $this->_leafs = array();
    }

    private function _rnd($min,$max) {
        return mt_rand($min,$max);
    }

    public function BSP(&$rootLeaf){
        $debugMode = get_func_debug_mode(__METHOD__);

        $_leafs = array();

        // $tmpLeaf; // helper Leaf

        // first, create a Leaf to be the ‘root’ of all Leafs.
        // $rootLeaf = new ksLeaf(0, 0, $w, $h);
        array_push($_leafs, $rootLeaf);

        $did_split = true;
        // we loop through every Leaf in our Vector over and over again, until no more Leafs can be split.
        while ($did_split) {
            $did_split = false;
            foreach ($_leafs as $tmpLeaf) {
                if ($tmpLeaf->leftChild == null && $tmpLeaf->rightChild == null) // if this Leaf is not already split…
                {
                    if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() '.$tmpLeaf->w.', '.$tmpLeaf->h. PHP_EOL; 
                    // if this Leaf is too big, or 75% chance…
                    if ($tmpLeaf->w > $this->MAX_LEAF_SIZE || $tmpLeaf->h > $this->MAX_LEAF_SIZE || $this->_rnd(1,100) > 25){
                        // split the Leaf!
                        if($tmpLeaf->split()){
                            if($debugMode) echo 'DEBUG: ' . __METHOD__ . '() '.$tmpLeaf->w.', '.$tmpLeaf->h.' split ! '. PHP_EOL; 
                            // if we did split, push the child leafs to the Vector so we can loop into them next
                            array_push($_leafs, $tmpLeaf->leftChild);
                            array_push($_leafs, $tmpLeaf->rightChild);
                            $did_split = true;
                        }
                    }
                }
            }
        }
        return $_leafs;
    }

}
